package com.github.yangyishe.p200;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 139. 单词拆分
 * https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
 *
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 *
 *
 *
 * 示例 1：
 *
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
 * 示例 2：
 *
 * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
 *      注意，你可以重复使用字典中的单词。
 * 示例 3：
 *
 * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出: false
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 300
 * 1 <= wordDict.length <= 1000
 * 1 <= wordDict[i].length <= 20
 * s 和 wordDict[i] 仅由小写英文字母组成
 * wordDict 中的所有字符串 互不相同
 */
public class Problem139 {
    public static void main(String[] args) {
        String s="catsandog";
        List<String> wordDict= Arrays.asList("cats", "dog", "sand", "and", "cat");

        Problem139 problem139 = new Problem139();
        boolean wordBreak = problem139.wordBreak(s, wordDict);
        System.out.println("wordBreak = " + wordBreak);

    }

    /**
     * 思路:
     * 1. s.length()==1, 查找字典中是否有合适的word, 直接返回, 记为result(1)=search(0,1)
     * 2. s.length()==2, result(2)=(result(1)&&search(1,2))||search(0,2)
     * 3. s.length()==3, result(3)=search(0,3)||(result(1)&&search(1,3))||(result(2)&&search(2,3))
     *
     * 其中,search方法可通过size和set两种方式优化判断效率
     *
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        //1. 创建判断表
        boolean[] judges=new boolean[s.length()];

        //2. 初始化字典
        initDict(wordDict);

        //3. 遍历推进判断
        for(int i=0;i<s.length();i++){
            boolean temp=search(s,0,i+1);
            for(int j=0;j<i;j++){
                if(temp){
                    break;
                }
                temp=(judges[j]&&search(s,j+1,i+1));
            }
            judges[i]=temp;
        }

        return judges[s.length()-1];
    }

    private void initDict(List<String> wordDict){
        for (String word : wordDict) {
            wordSet.add(word);
            maxLen=Math.max(maxLen,word.length());
            minLen=Math.min(minLen,word.length());
        }
    }

    private Set<String> wordSet=new HashSet<>();
    private int maxLen=0;
    private int minLen=Integer.MAX_VALUE;

    private boolean search(String content,int start,int end){
        int wordLen=end-start;
        if(wordLen>maxLen||wordLen<minLen){
            return false;
        }

        return wordSet.contains(content.substring(start,end));
    }
}
